package puzzle.projecteuler.p200;

public class Problem138B {

	/**
	 * 假设边长分别是a, a+k, k*c
	 * => a^2 + (a+k)^2 = (k*c)^2
	 * => (2a + k)^2 = (2c^2 - 1)*k^2
	 * => 2c^2 - 1 = d^2, a = (d-1)/2 * k
	 *    
	 * Pell方程2x^2 - y^2 = 1的解是x=c,y=d
	 * 那么三边分别是
	 * a = (d-1)/2 * k
	 * a+k = (d+1)/2 * k
	 * k*c 
	 * 换言之，周长l = (d+c)*k <= L 
	 * 并且必须满足 k>=1, d>=3
	 * 
	 * Pell方程的解满足：
	 *    c*sqrt(2) + d = (2*sqrt(2)+3)^n
	 * => c_n = 3*c_(n-1) + 2*d_(n-1)
	 *    d_n = 4*c_(n-1) + 3*d_(n-1)
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		long L = 100000000;
		long c = 5;
		long d = 7;
		long count = 0;
		while (c + d < L) {
			count += Math.floor((L-1)/(c+d));
			long x = c;
			c = 3*c+2*d;
			d = 4*x+3*d;
		}
		System.out.println(count);
	}

}
